package SwordFingerOffer;

public class Q52_ListIntersectionNode {
    //两个链表的公共节点
    //这种题是必须要做到秒杀的

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        //双指针
        ListNode pA = headA;
        ListNode pB = headB;

        //追平两条链表的长度
        int n = 0;
        while (pA != null){
            pA = pA.next;
            n++;
        }
        while (pB != null){
            pB = pB.next;
            n--;
        }

        //A长
        pA = headA;
        pB = headB;
        if (n > 0){
            while (n != 0){
                pA = pA.next;
                n --;
            }
        }else if (n < 0){
           //A短
            while (n != 0){
                pB = pB.next;
                n ++;
            }
        }

        while (pA != null && pB != null){
            if (pA == pB){
                return pA;
            }
            pA = pA.next;
            pB = pB.next;
        }

        return null;
    }

    public static void main(String[] args) {
        Q52_ListIntersectionNode fun = new Q52_ListIntersectionNode();
        ListNode A = new ListNode(4);
        A.next = new ListNode(1);
        A.next.next = new ListNode(8);
        A.next.next.next = new ListNode(4);
        A.next.next.next.next = new ListNode(5);
        ListNode B = new ListNode(5);
        B.next = new ListNode(0);
        B.next.next = new ListNode(1);
        B.next.next.next = new ListNode(8);
        B.next.next.next.next = new ListNode(4);
        B.next.next.next.next.next = new ListNode(5);
        System.out.println(fun.getIntersectionNode(A, B));
    }
}
